#include "DynamicArray.h"
#include <iostream>
#include <math.h>

DynamicArray::DynamicArray() : size(0), capacity(10)
{
    array = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &a)
{
    // std::cout<<"aaaaaaa";
    this->size = a.size;
    this->capacity = a.capacity;
    this->array = new ElementType[capacity];
    for (size_t i = 0; i < size; i++)
    {
        this->array[i] = a.array[i];
    }
    // return *this;
}

DynamicArray &DynamicArray::operator=(const DynamicArray &a)
{
    // std::cout<<"bbbbbbbb"<<std::endl;
    delete[] array;
    this->size = a.size;
    this->capacity = a.capacity;
    this->array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        this->array[i] = a.array[i];
    }
    return *this;
}

DynamicArray::~DynamicArray()
{
    delete[] array;
}

// 复杂度：不扩容O(1)  扩容O(N)
void DynamicArray::InsertTail(const ElementType &element)//尾插法
{
    if (size == capacity)
    {
        capacity *= 2;
        ReSize(capacity);
    }

    array[size] = element;
    size++;
}

// 复杂度O(n)
void DynamicArray::InsertHead(const ElementType &element)//头插法
{
    if (size == capacity)
    {
        capacity *= 2;
        ReSize(capacity);
    }
    for (size_t i = size; i > 0; i--)
    {
        array[i] = array[i - 1];
    }
    array[0] = element;
    size++;
}

void DynamicArray::InsertByIndex(const ElementType &element, size_t index)//中间插入
{
    if (index > size)
    {
        std::cout << "位置非法" << std::endl;
        return;
    }
    if (size == capacity)
    {
        capacity *= 2;
        ReSize(capacity);
    }
    for (size_t i = size; i > index; i--)
    {
        array[i] = array[i - 1];
    }
    array[index] = element;
    size++;
}

// 复杂度O(n)
void DynamicArray::RemoveByIndex(size_t index)  ////按位置删除
{
    if (index >= size)
    {
        std::cout << "位置非法" << std::endl;
    }

    for (size_t i = index; i < size - 1; i++)
    {
        array[i] = array[i + 1];
    }
    size--;
}

// O(n^2)
void DynamicArray::RemoveByElement(const ElementType &element)  //按值删除
{
    for (size_t i = 0; i < size; i++)
    {
        if (array[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 复杂度O(1)
ElementType *DynamicArray::FindByIndex(size_t index)     //按位置查找
{
    if (index >= size)
    {
        return nullptr;
    }

    return &array[index];
}

DynamicArray DynamicArray::FindByElement(const ElementType &element)    //按值查找
{
    DynamicArray result;
    for (size_t i = 0; i < size; i++)
    {
        if (array[i] == element)
        {
            result.InsertTail(i);
        }
    }
    return result;
}

// O(1)
void DynamicArray::UpdateByIndex(size_t index, const ElementType &element)  //按位置修改
{
    if (index >= size)
    {
        std::cout << "位置非法" << std::endl;
    }

    array[index] = element;
}

// O(n)
void DynamicArray::UpdateByElement(const ElementType &oldelement, const ElementType &newelement)//按值修改
{
    for (size_t i = 0; i < size; i++)
    {
        if (array[i] == oldelement)
        {
            UpdateByIndex(i, newelement);
        }
    }
}

ElementType &DynamicArray::operator[](int index)
{
    return array[index];
}

void DynamicArray::Sort()   //排序算法
{
    FastSort(0,size-1,0,2 * log2(size));
}

void DynamicArray::Duplicate()      //O(n) 有序数列去重算法
{
    for(size_t i = 1;i < size; i++)
    {
        if(array[i] == array[i-1])
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

DynamicArray DynamicArray::Merge(const DynamicArray &a) //O(n) //归并排序
{
    DynamicArray result;
    size_t first =0;//当前数组
    size_t second =0;//传进来的数组    
    while(first<this->size && second<a.size)         
    {
        if(array[first]< a.array[second])
            result.InsertTail(array[first++]);
        else
            result.InsertTail(a.array[second++]);
    }
    while(first<this->size)
      result.InsertTail(array[first++]);
    while(second< a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

DynamicArray DynamicArray::FdInterSctn(const DynamicArray &a)   //交集
{ 
    DynamicArray result;
    size_t first =0;//当前数组
    size_t second =0;//传进来的数组    
    while(first<this->size && second<a.size) 
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(array[first]< a.array[second])
        {
            first++;
        }

        else if(array[first]>a.array[second])
        {
            second++;
        }
    }
    return result;
}

DynamicArray DynamicArray::FindUnionSet(const DynamicArray &a)      //并集
{
    DynamicArray result;
    size_t first =0;//当前数组
    size_t second =0;//传进来的数组    
    while(first<this->size && second<a.size) 
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }

        else if(array[first] < a.array[second])
        {
            result.InsertTail(array[first++]);
        }

        else if(array[first] > a.array[second])
        {
            result.InsertTail(array[second++]);
        }
    }
    while(first<this->size)
        result.InsertTail(array[first++]);
    while(second< a.size)
        result.InsertTail(a.array[second++]);
    
    return result;
}

DynamicArray DynamicArray::Findpifference(const DynamicArray &a)    //取补集
{
    DynamicArray result;
    size_t first =0;//当前数组
    size_t second =0;//传进来的数组    
    while(first<this->size && second<a.size) 
    {
        if(array[first] == a.array[second])
        {
            first++;
            second++;
        }

        else if(array[first] < a.array[second])
        {
            result.InsertTail(array[first++]);
        }

        else if(array[first] > a.array[second])
        {
            result.InsertTail(array[second++]);
        }
    }
    while(first<this->size)
        result.InsertTail(array[first++]);
    while(second< a.size)
        result.InsertTail(a.array[second++]);
    return  result;
}

bool DynamicArray::operator==(const DynamicArray &a)    //O(n)//判断两个数列是否相等
{
    if(size != a.size)
        return false; 
    size_t first =0;//当前数组
    size_t second =0;//传进来的数组 
    while(first<this->size && second< a.size)
    {
        if(array[first++]!= a.array[second++])
            return false;
    }
    return false;
}

size_t DynamicArray::BinarySearch(const ElementType &element)
{
    size_t left = 0;
    size_t right = size - 1;
    while(left = size -1);
    {
        size_t mid=left+(right-left )/2;
        if(array[mid]==element)
        {
            return mid;
        }
        else if(array[mid]>element)
        {
            if(mid==0)
                return ULONG_MAX;
            right = mid-1;
        }
        else
        {
            left = mid+1;
        }
    }
    return ULONG_MAX;
}

bool DynamicArray::Contains(const DynamicArray &a)
{
    // DynamicArray s = FdInterSctn(a);
    // return s = a;
    size_t j=0;
    for(size_t i=0;i< size; i++)
    {
        if(array[i]== a.array[j])
        j++;
    }
    return j == a.size;

}

bool DynamicArray::ContnsContains(const DynamicArray &a)
{
    for(int i=0;i<=size - a.size; i++)
    {
        if(SubSquence(i,a.size)==a)
        {
            return true;
        }
    }
    return false;
}

DynamicArray DynamicArray::SubSquence(size_t index, size_t len)
{
    DynamicArray result;
    if(index+len>size)
        return result;

    for(size_t i = 0;i<len;i++)
    {
        result.InsertTail(array[index+i]);
    }
    return result;
}

size_t DynamicArray::partition(size_t start, size_t end)    //分组函数
{
    size_t left = start;
    size_t right = end;
    ElementType tmp = array[start];
    while(left < right)
    {
        while(array[right]>tmp && left< right)
            right--;
        if(left< right)
            array[left++]= array[right];

        while(array[left]<tmp && left< right)
            left++;
        if(left< right)
            array[right--]= array[left];
    }
    array[left] = tmp;
    return left;
}

void DynamicArray::FastSort(size_t start, size_t end,size_t CurDepth,size_t MaxDepth)   
{
    if(start >= end)
        return;

    //如果没有达到最大的递归深度
    if(CurDepth<MaxDepth)
    {
        size_t par = partition(start,end);//对数列分组
        if(par !=0)
            FastSort(start,par-1,CurDepth+1,MaxDepth);
        FastSort(par+1,end,CurDepth+1,MaxDepth);
    }
    //超过最大深度,改用插入排序
    else
    {
        std::cout<<"插入排序"<<std::endl;
        InsertSort(start,end);
    }
}

void DynamicArray::InsertSort(size_t start, size_t end)     //插入排序
{
    for(size_t i=start+1;i<=end;i++)
    {
        size_t j=i;
        ElementType tmp = array[i];
        for(; j>start;j--)
        {
            if(array[j-1]>tmp)
                array[j]=array[j-1];
            else
                break;
        }
        array[j]=tmp;
    }
}

void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    this->size = size > capacity ? capacity : size;
    ElementType *p = new ElementType[capacity];
    for (size_t i = 0; i < size; i++)
    {
        p[i] = array[i];
    }
    delete[] array;
    array = p;
}

void DynamicArray::show()
{
    for (size_t i = 0; i < size; i++)
    {
        std::cout << array[i] << "  ";
    }
    std::cout << std::endl;
}